AVL Tree

AVL 트리
균형이 갖춰진 이진 트리(Binary Tree)를 의미한다.
검색에 있어서 O(logN)의 시간 복잡도를 유지할 수 있다.

AVL 트리는 균형 인수(Balance Factor)라는 개념을 이용한다
( 균형 인수= abs(왼쪽 자식높이 - 오른쪽 자식높이) )

균형 인수가 2이상일 때, 이상이 있는 AVL 트리임.
AVL 트리는 모든 노드에 대한 균형 인수가 +1, 0, -1만 허용
균형 인수가 허용치를 벗어나면, 회전(Rotation)을 통해 트리를 재구성 해야 한다.
AVL 형식의 균형이 깨질 수 있는 경우
1) LL형식
2) LR형식
3) RR형식
4) RL형식
#include <stdio.h>
#include <stdlib.h>
int getMax(int a, int b){
if(a>b) return a;
return b;
}
typedef struct{
int data;
int height;
struct Node* leftChild;
struct Node* rightChild;
}Node;
int getHeight(Node* node){
if(node==NULL)return 0;
return node->height;
}
void setHeight(Node* node){
node->height= getMax(getHeight(node->leftChild), getHeight(node->rightChild))+1;
}
int getDifference(Node* node){
if(node==NULL) return 0;
Node* leftChild=node->leftChild;
Node* rightChild=node->rightChild;
return getHeight(leftChild)-getHeight(rightChild);
}
Node* rotateLL(Node* node){
Node* leftChild=node->leftChild;
node->leftChild=leftChild->rightChild;
leftChild->rightChild=node;
setHeight(node);
return leftChild;
}
Node* rotateRR(Node* node){
Node* rightChild=node->rightChild;
node->rightChild=rightChild->leftChild;
rightChild->leftChild=node;
setHeight(node);
return rightChild;
}
Node* rotateLR(Node* node){
Node* leftChild=node->leftChild;
node->leftChild=rotateRR(leftChild);
return rotateLL(node);
}
Node* rotateRL(Node* node){
Node* rightChild=node->rightChild;
node->rightChild=rotateLL(rightChild);
return rotateRR(node);
}
Node *balance(Node* node){
int difference=getDifference(node);
if(difference>=2){
if(getDifference(node->leftChild)>=1){
node=rotateLL(node);
}
else{
node=rotateLR(node);
}
}
else if(difference<=-2){
if(getDifference(node->rightChild)<=-1){
node=rotateRR(node);
}
else{
node=rotateRL(node);
}
}
setHeight(node);
return node;
}
Node *insertNode(Node* node, int data){
if(!node){
node=(Node*)malloc(sizeof(Node));
node->data=data;
node->height=1;
node->leftChild=node->rightChild=NULL;
}
else if(data<node->data){
node->leftChild=insertNode(node->leftChild, data);
node=balance(node);
}
else if(data>node->data){
node->rightChild=insertNode(node->rightChild, data);
node=balance(node);
}
else{
printf("데이터 중복이 발생했습니다.\n");
}
return node;
}
Node* root=NULL;
void display(Node* node, int level){
if(node!=NULL){
display(node->rightChild, level+1);
printf("\n");
if(node==root){
printf("Root: ");
}
for(int i=0;i<level && node !=root; i++){
printf(" ");
}
printf("%d(%d)", node->data, getHeight(node));
display(node->leftChild, level+1);
}
}
int main(void){
root=insertNode(root, 7);
root=insertNode(root, 6);
root=insertNode(root, 5);
root=insertNode(root, 3);
root=insertNode(root, 1);
root=insertNode(root, 9);
root=insertNode(root, 8);
root=insertNode(root, 12);
root=insertNode(root, 16);
root=insertNode(root, 18);
root=insertNode(root, 23);
root=insertNode(root, 21);
root=insertNode(root, 14);
root=insertNode(root, 15);
root=insertNode(root, 19);
root=insertNode(root, 20);
display(root,1); printf("\n");
system("pause");
return 0;
}